1
La puissance des relations de récurrence
MATH002Lesson 7
00:00
Les relations de récurrence agissent comme un pont mathématique profond entre les définitions récursives et les solutions fonctionnelles explicites, capturant l'essence de Diviser pour régner des stratégies. En définissant des suites par des étapes auto-référentielles, nous modélisons tout, des structures combinatoires comme les nombres de Stirling et de Catalan jusqu'à la croissance hyper-exponentielle de la fonction d'Ackermann.

1. Diversité combinatoire

La véritable puissance des récurrences réside dans la diversité des suites qu'elles gouvernent. Par exemple, les nombres de Stirling de seconde espèce sont définis par :

$$S_{n+1,k} = S_{n,k-1} + nS_{n,k}$$

Ces nombres comptent le nombre de façons de partitionner un ensemble de $n+1$ éléments en $k$ sous-ensembles non vides. De même, nombres de Catalan ($C_n$) décrivent la triangulation des polygones convexes — diviser un pentagone convexe en triangles à l’aide de diagonales non intersectantes.

2. Modélisation structurelle et dérangements

Les récurrences offrent un cadre rigoureux pour des problèmes de dénombrement peu évidents, tels que les dérangements. Le nom technique d'une permutation où aucun élément n'est à sa position initiale est un dérangement ($D_n$).

La relation de récurrence des dérangements

La relation pour les dérangements est donnée par :

$$D_n - nD_{n-1} = (-1)^n$$

Ou de manière alternative : $D_n = (n-1)(D_{n-1} + D_{n-2})$. Cela compte le nombre de façons dont $n$ personnes peuvent recevoir un chapeau erroné à une borne de vestiaire.

3. Les limites de croissance et de complexité

Les récurrences définissent à la fois les algorithmes ultra-efficients et ceux « explosifs » du point de vue computationnel :

  • Approche « diviser pour régner » : La recherche binaire est modélisée par $a_n = c a_{n/m} + d$, ce qui donne un temps d'exécution logarithmique.
  • La fonction d'Ackermann : Définit une profondeur récursive qui croît plus vite que toute fonction polynomiale ou exponentielle : $$AO(x + 3, y, z + 1) = AO(x + 2, y, AO(x + 3, y, z))$$
🎯 Résumé technique du professeur
Lorsqu'on traite des relations non homogènes, souvenez-vous de la forme $U_n = V_n + g(n)$, où $V_n$ est la solution homogène. Pour les relations linéaires homogènes à coefficients constants comme $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, trouvez les racines de l'équation caractéristique $t^2 - c_1 t - c_2 = 0$.